The subject matter disclosed herein generally relates to motion planning systems, and more particularly to kinematic motion planning with regional planning constraints.
Motion planning for a vehicle, e.g., an autonomous vehicle, typically involves construction of a graph or tree that represents feasible paths to various locations in an area under consideration. A common approach for motion planning is computing an obstacle free path (kinematic planning) and then computing a point-wise velocity and heading (dynamic planning) on the paths that respect vehicle dynamic and mission constraints. The two-step procedure allows constraints and problems in kinematic space to be dealt with independent of the dynamic space and leads to a well-defined dynamic problem due to specification of a curve in space. Solvers that are specialized in each space can be brought to bear and implemented efficiently, leading to a fast motion planning architecture. However, paths computed using kinematic motion planning may not be dynamically achievable by the vehicle with respect to velocity and heading constraints. For example, a kinematic path may have a bend shortly after the start point that may not be achievable given a start velocity and deceleration limits of the vehicle.
One approach to merging kinematic planning and dynamic planning involves a one-step process. However, attempting to completely merge kinematic planning and dynamic planning can increase the computation requirements exponentially (i.e., one extra dimension) and limits the use of many existing robust kinematic path solvers—leaving more complicated nonlinear optimization-based approaches that lack efficiency and solution guarantees.